package com.salim.leetcode.$143;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class ReorderList {
    //这道题还有多种做法
    //其中一种 三步
    //第一步 找到中间
    //第二步 将右边反转
    //第三步 将左右交替拼接
    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        Deque<ListNode> queue = new LinkedList<>();
        ListNode point = head;
        while (point!=null){
            queue.add(point);
            point = point.next;
        }
        //先出头部
        queue.pollFirst();
        while (!queue.isEmpty()){
            head.next = queue.pollLast();
            head = head.next;
            if(!queue.isEmpty()){
                head.next = queue.pollFirst();
                head = head.next;
            }
        }
        //最后一个元素去掉next防止循环
        head.next = null;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
